//
// Created by Jisam on 10/10/2024 19:31.
// Solution of  P1020 [NOIP1999 提高组] 导弹拦截
// 2024-10-10 20:14:40 AC 100 线性DP + Dilworth 定理 + 贪心
#include <bits/stdc++.h>

#define  int long long
#define  endl "\n"
#define  all(x) (x).begin(),(x).end()
#define  pb push_back
using namespace std;
const int MAXN = 1e5 + 5;
int a[MAXN];
int g[MAXN];
int x;
int n;
int cnt;
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);  // 关闭cin和cout的同步，提高输入输出效率
    while (cin >> x) {  // 循环读取输入的导弹高度，直到输入结束
        a[++n] = x;  // 将读取的导弹高度存储到数组a中，并更新导弹数量n
    }
    g[0]  = 2e9;  // 初始化g数组的第一个元素为一个很大的数，用于后续的二分查找插入

    // 第一次遍历，按照从小到大的顺序插入导弹高度到g数组中
    for(int i = 1; i <= n ; i ++) {
        if(a[i] <= g[cnt]) g[++cnt] = a[i];  // 如果当前导弹高度小于等于g数组中的最后一个元素，则直接插入
        else {
            int l = 0, r = cnt + 1;  // 初始化二分查找的左右边界
            while(l + 1 < r){  // 执行二分查找
                int mid = (l + r) / 2;  // 计算中间位置
                (g[mid] < a[i] ? r : l) = mid;  // 更新左右边界
            }
            g[r] = a[i];  // 插入当前导弹高度到g数组中
        }
    }
    cout << cnt << endl;  // 输出第一次遍历后g数组中的元素数量

    cnt = 0;  // 重置cnt为0
    g[0] = -2e9;  // 初始化g数组的第一个元素为一个很小的数，用于后续的二分查找插入

    // 第二次遍历，按照从大到小的顺序插入导弹高度到g数组中
    for(int i = 1; i <= n ; i ++){
        if(a[i] > g[cnt]) g[++cnt] = a[i];  // 如果当前导弹高度大于g数组中的最后一个元素，则直接插入
        else {
            int l = 0, r = cnt + 1;  // 初始化二分查找的左右边界
            while(l + 1 < r){  // 执行二分查找
                int mid = (l + r) / 2;  // 计算中间位置
                (g[mid] >= a[i] ? r : l) = mid;  // 更新左右边界
            }
            g[r] = a[i];  // 插入当前导弹高度到g数组中
        }
    }
    cout << cnt << endl;  // 输出第二次遍历后g数组中的元素数量
    return 0;  // 程序结束
}